package com.fang.algorithm.zuo.linked;

/**
 * @author fanglingxiao
 * @version 1.0
 * @description 两个链表相加
 * 1->2->3->4
 * 2->9->8
 * 4321 + 892 = 5213
 * 得到
 * 3->1->2->5
 * @date 2022/4/23 12:28 上午
 **/
public class Test07_AddTwoLinkedList {

    public static class Node {
        private int value;
        private Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        node1.next = new Node(2);
        node1.next.next = new Node(3);
        node1.next.next.next = new Node(4);
        Node node2 = new Node(2);
        node2.next = new Node(9);
        node2.next.next = new Node(8);
        printNode(node1);
        printNode(node2);
        Node addNode = addTwoLinkedList(node1, node2);
        printNode(addNode);
    }

    private static Node addTwoLinkedList(Node head1, Node head2) {
        int size1 = calcLinkedListSize(head1);
        int size2 = calcLinkedListSize(head2);
        Node l = size1 >= size2 ? head1 : head2;
        Node s = size1 < size2 ? head1 : head2;
        Node currL = l;
        Node currS = s;
        Node lastL = currL;
        int carry = 0;
        int currNum = 0;
        while (currS != null) {
            int sum = currL.value + currS.value + carry;
            currNum = sum % 10;
            carry = sum / 10;
            currL.value = currNum;

            lastL = currL;
            currS = currS.next;
            currL = currL.next;
        }
        while (currL != null) {
            int sum = currL.value + carry;
            currNum = sum % 10;
            carry = sum / 10;
            currL.value = currNum;

            lastL = currL;
            currL = currL.next;
        }
        if (carry != 0) {
            // lastL的作用是currL为空是找不到当前此节点
            lastL.next = new Node(carry);
        }
        return l;
    }

    private static int calcLinkedListSize(Node node) {
        int size = 0;
        while (node != null) {
            size++;
            node = node.next;
        }
        return size;
    }


    private static void printNode(Node reverseNode) {
        while (reverseNode != null) {
            System.out.print(reverseNode.value + "->");
            reverseNode = reverseNode.next;
        }
        System.out.println();
    }
}
